#include "min_list.h"
#include <stdio.h> //just for print_minlist
#include <string.h>
#include <stdlib.h>

int compare_minlist(struct minlist_entry* A, struct minlist_entry* B){
    if(A == NULL || B == NULL)
        return -1;
        
    if(A->distance > B->distance)
        return 1;
    return 0; //当相同时，也会返回0。这个做法是基于ANN中当两个点距离相同时，覆盖掉旧的点可能更好因为旧的点的邻居可能已经被查询过了，新的点有更多潜在邻居
}

struct minlist* create_minlist(int size){
    void* mem = malloc(sizeof(struct minlist)+size*sizeof(struct minlist_entry));
    memset(mem, 0, sizeof(struct minlist)+size*sizeof(struct minlist_entry));
    if(mem == NULL)
        return NULL;
    struct minlist* minlist = (struct minlist*)mem;
    minlist->size = size;
    minlist->count = 0;
    minlist->calculate_k = 0;
    minlist->entries = (struct minlist_entry*)((char*)mem+sizeof(struct minlist)); //point entries to later mem

    return minlist;
}

int insert_minlist(struct minlist* list, struct minlist_entry* entry){
    if(list == NULL || entry == NULL)
        return -1;

    //0.首先是判断这个数据是否之前出现过
    for(int i=0; i<list->count; i++){
        if(entry->id == list->entries[i].id){
            return -1;
        }
    }

    //1.给新数据找到位置
    int index = -1;
    if(list->count < list->size){ //没有填满，直接插入在末尾即可
        index = list->count;
        list->count++;
    }
    else{ //填满了，那么和末尾的数据比较，如果比末尾数据小的话直接占领末尾数据的位置即可
        if(compare_minlist(entry, &(list->entries[list->size-1]))==0)
            index = list->size-1;
        else
            return -1;
    }
    
    //2.拷贝数据
    memcpy(&(list->entries[index]), entry, sizeof(struct minlist_entry));

    //3.然后把新数据插入到链表中
    //复杂度为O(n/2)。虽然是O(n)的但是候选列表一般不会很长(通常10-50)，O(n/2)相比O(logn)增加的时间不是很多
    struct minlist_entry tmp; //用于交换
    for(int i=0; i<list->count-1; i++){ 
        if(compare_minlist(&(list->entries[index]),&(list->entries[index-1]))==0){
            memcpy(&tmp, &(list->entries[index]),sizeof(struct minlist_entry));
            memcpy(&(list->entries[index]),&(list->entries[index-1]),sizeof(struct minlist_entry));
            memcpy(&(list->entries[index-1]), &tmp, sizeof(struct minlist_entry));

            index--; //当前新数据在index
        }
        else{
            return index;
        }
    }

    return 0;
}  

struct minlist_entry* get_mins(struct minlist* list){
    return list->entries;
}

void print_minlist(struct minlist* list){
    if(list == NULL)
        return;
    printf("minlist:");
    for(int i=0; i<list->size; i++){
        printf("(%d:%f)-",list->entries[i].id,list->entries[i].distance);
    }
    printf("\n");
}

void destory_minlist(struct minlist* list){
    free(list);
}

int get_minlist_id(struct minlist* list, int index){
    return list->entries[index].id; 
}